package com.jiang.专题.动态规划.Q139;

import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/27 22:21
 */
class Solution {
    // 递归（超时）
    // public boolean wordBreak(String s, List<String> wordDict) {
    //     return wordJudge(s, wordDict, 0);
    // }

    // private boolean wordJudge(String s, List<String> wordDict, int from) {
    //     if (from == s.length()) {
    //         return true;
    //     }
    //     int strat = from;
    //     boolean flag = false;
    //     while (from < s.length()) {
    //         String temp = s.substring(strat, from + 1);
    //         if (wordDict.contains(temp) && wordJudge(s, wordDict, from + 1)) {
    //             flag = true;
    //             break;
    //         }
    //         from++;
    //     }
    //     return flag;
    // }

    // 动态规划
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1]; // dp[i]为true，表示前i个字符能由wordDict构成
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}
